#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include"Stack.h"
void print(int* a, int n)
{
	int i = 0;
	for (i = 0;i < n;i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void Swap(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

int PartSort3(int* a, int begin, int end)
{
	int keyi = begin;
	int prev = begin;
	int cur = begin + 1;
	while (cur <= end)
	{
		if (a[cur] < a[keyi] && ++prev != a[cur])
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[prev], &a[keyi]);
	keyi = prev;
	return keyi;
}

void QuickSortNonR(int* a, int begin, int end)
{
	Stack s;
	StackInit(&s);
	StackPush(&s, end);
	StackPush(&s, begin);
	while (!StackEmpty(&s))
	{
		int left = StackTop(&s);
		StackPop(&s);
		int right = StackTop(&s);
		StackPop(&s);
		int keyi = PartSort3(a, left, right);
		//[left,keyi-1]keyi[keyi+1,right]
		if (left < keyi - 1)
		{
			StackPush(&s, keyi - 1);
			StackPush(&s, left);
		}
		if (keyi + 1 < right)
		{
			StackPush(&s, right);
			StackPush(&s, keyi+1);
		}
	}
	StackDestroy(&s);
}
int main()
{
	int a[] = { 99,45,33,67,12,87,123,32,1 };
	int n = sizeof(a) / sizeof(a[0]);
	print(a, n);
	QuickSortNonR(a, 0, n - 1);
	print(a, n);
	return 0;
}